public class Sort {
    //归并排序
    public static void mergeSort(int[] array){
        mergeSortFunc(array, 0, array.length - 1);
    }
    //递归
    public static void mergeSortFunc(int[] array, int left, int right){
        if (left >= right){
            return;
        }
        int mid = (right + left) / 2;
        mergeSortFunc(array, left, mid);
        mergeSortFunc(array, mid + 1, right);
        merge(array, left, mid, right);
    }
    //合并两个有序数组
    public static void merge(int[] array, int left, int mid, int right){
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int[] tmpArray = new int[right - left + 1];
        int k = 0;//用于遍历tmpArray数组
        //组合有序数组
        while (s1 <= e1 && s2 <= e2){
            if (array[s1] <= array[s2]){
                tmpArray[k++] = array[s1++];
            }
            if (array[s2] <= array[s1]){
                tmpArray[k++] = array[s2++];
            }
        }
        while (s1 <= e1){
            tmpArray[k++] = array[s1++];
        }
        while (s2 <= e2){
            tmpArray[k++] = array[s2++];
        }

        //将有序数组tmpArray传给原数组array
        for (int i = 0; i < k; i++) {
            array[i + left] = tmpArray[i];
        }
    }
    //非递归实现归并排序
    //时间复杂度：O（n*logn)
    //空间复杂度：O（n)
    //稳定性：稳定的
    public static void mergeSort1(int[] array){
        int gap = 1;
        while (gap < array.length) {
            for (int i = 0; i < array.length; i = i + gap*2) {
                int left = i;
                int mid = left + gap -1;
                int right = mid + gap;
                //mid和right可能会越界
                if (mid >= array.length){
                    mid = array.length - 1;
                }
                if (right >= array.length){
                    right = array.length - 1;
                }
                merge(array, left, mid, right);
            }
            gap*=2;
        }
    }

    public static void main(String[] args) {

    }
}
